﻿<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" >
<head>
    <title>Untitled Page</title>

     <script type="text/javascript">
 <!--        
    var n = 5;
    var arr =[];

    for (var i=0; i<n+1; i++){arr.push(i);}

    function check(arr,n){    
        for(var i=0;i<n;){
            if (arr[i]==arr[arr[i]]){
                if (arr[i]!=i){ return true;}
                i++;
            }else{
                var t=arr[arr[i]];
                arr[arr[i]]=arr[i];
                arr[i]=t;
            }
        }

        return false;
    }

    document.write("数组：" + arr  +"<BR>");
    document.write(check(arr,n+1)?"有重复":"无重复"); 

    arr[1] = 2;
    arr[3] = 2;    
    document.write("<BR><BR>数组：" + arr  +"<BR>");
    document.write(check(arr,n+1)?"有重复":"无重复"); 
 //-->
 </script>
</head>
<body>
    一个下标0-n的数组 内容是0-n的整数
    编写一函数判断它是否有重复元素

    最优算法实现时间复杂度为O(n)空间复杂度为O(1)
</body>
</html>
